Plus one linked list [Two Pointers]

Time: O(N); Space: O(1); medium

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example 1:

Input: head = {ListNode} 1->2->3->None

Output: {ListNode} 1->2->4->None

Explanation:

  • 123 + 1 = 124

Example 2:

Input: {ListNode} 9->9->None

Output: {ListNode} 1->0->0->None

Explanation:

  • 99 + 1 = 100

[6]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

1. Two pointers solution

[7]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None

        dummy = ListNode(0)
        dummy.next = head

        left, right = dummy, head
        while right.next:
            if right.val != 9:
                left = right
            right = right.next

        if right.val != 9:
            right.val += 1
        else:
            left.val += 1
            right = left.next
            while right:
                right.val = 0
                right = right.next

        return dummy if dummy.val else dummy.next

[8]:

s = Solution1()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
res = s.plusOne(head)
exp = [1,2,4]
for val in exp:
    assert res.val == val
    res = res.next

head = ListNode(9)
head.next = ListNode(9)
res = s.plusOne(head)
exp = [1,0,0]
for val in exp:
    assert res.val == val
    res = res.next

2.

[9]:

class Solution2(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def reverseList(head):
            dummy = ListNode(0)
            curr = head
            while curr:
                dummy.next, curr.next, curr = curr, dummy.next, curr.next
            return dummy.next

        rev_head = reverseList(head)
        curr, carry = rev_head, 1
        while curr and carry:
            curr.val += carry
            carry = curr.val // 10
            curr.val %= 10
            if carry and curr.next is None:
                curr.next = ListNode(0)
            curr = curr.next

        return reverseList(rev_head)

[10]:

s = Solution2()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
res = s.plusOne(head)
exp = [1,2,4]
for val in exp:
    assert res.val == val
    res = res.next

head = ListNode(9)
head.next = ListNode(9)
res = s.plusOne(head)
exp = [1,0,0]
for val in exp:
    assert res.val == val
    res = res.next